package com.example.demo.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 链接 <a href="https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/description/?envType=daily-question&envId=2024-01-25">https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/description/?envType=daily-question&envId=2024-01-25</a><br>
 * <p>
 * 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
 * <p>
 * 请你用整数形式返回 nums 中的特定元素之 和 ，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。
 * <p>
 * 整数的二进制表示中的 1 就是这个整数的 置位 。
 * <p>
 * 例如，21 的二进制表示为 10101 ，其中有 3 个置位。
 */
public class _2859_计算K置位下标对应元素之和 {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(5);
        list.add(10);
        list.add(1);
        list.add(5);
        list.add(2);
        int i = new Solution().sumIndicesWithKSetBits(list, 1);
        System.out.println(i);
    }

    public static class Solution {

        public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
            int n = nums.size();
            int sum = 0;
            for (int i = 0; i < n; i++) {
                String binaryString = Integer.toBinaryString(i);
                int count = 0;
                for (int j = 0; j < binaryString.length(); j++) {
                    if (binaryString.charAt(j) == '1') {
                        count++;
                    }
                }
                if (count == k) {
                    sum += nums.get(i);
                }
            }
            return sum;
        }

        /**
         * 方法二：
         */
        public int sumIndicesWithKSetBits1(List<Integer> nums, int k) {
            int n = nums.size();
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if (Integer.bitCount(i) == k) {
                    sum += nums.get(i);
                }
            }
            return sum;
        }

        /**
         * 方法三：
         */
        public int sumIndicesWithKSetBits2(List<Integer> nums, int k) {
            int ans = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (bitCount(i) == k) {
                    ans += nums.get(i);
                }
            }
            return ans;
        }
        public int bitCount(int x) {
            int cnt = 0;
            while (x != 0) {
                cnt += (x % 2);
                x /= 2;
            }
            return cnt;
        }
    }
}
